翻訳と辞書 Words near each other ・ Mining in Ethiopia ・ Mining in Gabon ・ Mining in Georgia (country) ・ Mining in Hong Kong ・ Mining in India ・ Mining in Iran ・ Mining in Japan ・ Mining in Limburg ・ Mining in Mauritania ・ Minimum contacts ・ Minimum control speeds ・ Minimum crossing altitude ・ Minimum cut ・ Minimum daily balance ・ Minimum Data Set ・ Minimum degree algorithm ・ Minimum degree spanning tree ・ Minimum depth of occurrence ・ Minimum description length ・ Minimum design metal temperature ・ Minimum detectable signal ・ Minimum deviation ・ Minimum distance ・ Minimum distance estimation ・ Minimum efficiency reporting value ・ Minimum efficient scale ・ Minimum employer contribution ・ Minimum en route altitude ・ Minimum energy control ・ Minimum energy performance standard Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Minimum degree algorithm ： ウィキペディア英語版 Minimum degree algorithm In numerical analysis the minimum degree algorithm is an algorithm used to permute the rows and columns of a symmetric sparse matrix before applying the Cholesky decomposition, to reduce the number of non-zeros in the Cholesky factor. This results in reduced storage requirements and means that the Cholesky factor, or sometimes an incomplete Cholesky factor used as a preconditioner (for example in the preconditioned conjugate gradient algorithm) can be applied with fewer arithmetic operations. Minimum degree algorithms are often used in the finite element method where the reordering of nodes can be carried out depending only on the topology of the mesh, rather than the coefficients in the partial differential equation, resulting in efficiency savings when the same mesh is used for a variety of coefficient values. Given a linear system :$\backslash mathbf\backslash mathbf\; =\; \backslash mathbf$ where A is an $n\; \backslash times\; n$ real symmetric sparse square matrix the Cholesky factor L will typically suffer 'fill in', that is have more non-zeros than the upper triangle of A. We seek a permutation matrix P, so that the matrix $\backslash mathbf^T\backslash mathbf\backslash mathbf$, which is also symmetric, has the least possible fill in its Cholesky factor. We solve the reordered system :$\backslash left(\backslash mathbf^T\backslash mathbf\backslash mathbf\backslash right)\; \backslash left(\backslash mathbf^T\backslash mathbf\backslash right)\; =\; \backslash mathbf^T\backslash mathbf.$ The problem of finding the best ordering is an NP-complete problem and is thus intractable, so heuristic methods are used instead. The minimum degree algorithm is derived from a method first proposed by Markowitz in 1959 for non-symmetric linear programming problems, which is loosely described as follows. At each step in Gaussian elimination row and column permutations are performed so as to minimize the number of off diagonal non-zeros in the pivot row and column. A symmetric version of Markowitz method was described by Tinney and Walker in 1967 and Rose later derived a graph theoretic version of the algorithm where the factorization is only simulated, and this was named the minimum degree algorithm. The graph referred to is the graph with ''n'' vertices, with vertices ''i'' and ''j'' connected by an edge when $a\_\; \backslash ne\; 0$, and the ''degree'' is the degree of the vertices. A crucial aspect of such algorithms is a tie breaking strategy when there is a choice of renumbering resulting in the same degree. A version of the minimum degree algorithm was implemented in the MATLAB function symmmd (where MMD stands for multiple minimum degree), but has now been superseded by a symmetric approximate multiple minimum degree function symamd, which is faster. This is confirmed by theoretical analysis, which shows that for graphs on ''n'' vertices and ''m'' edges, MMD has a tight upper bound of $O(n^2m)$ on its run time, whereas for AMD a tight bound of $O(nm)$ holds. ==References== * * * * * 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Minimum degree algorithm」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.